; 3.15 最短路径 Shorttest Path

; 网络节点用符号表示，网络的关联用以下形式表示
; (node . neighbors)

; 一个网络
(setf min '((a b c) (b c) (c d)))

; 最短路径
; start 起点
; end 终点
; net 网络
(defun shortest-path (start end net)
	(bfs end (list (list start)) net))

(defun bfs (end queue net)
	(if (null queue)
		nil
		(let ((path (car queue)))
			(let ((node (car path)))
				(if (eql node end)
					(reverse path)
					(bfs end
							 (append (cdr queue)
											 (new-paths path node net))
							 net))))))

(defun new-paths (path node net)
	(mapcar #'(lambda (n)
							(cons n path))
					(cdr (assoc node net))))
